/**
 * 
 */
package zhoujian.oj.leetcode;

import static org.junit.Assert.*;
import static org.hamcrest.Matchers.*;

import org.junit.Test;

/**
 * @author hyper
 * @email zjkermit@gmail.com
 * @date Dec 26, 2013
 * @version 1.0
 * @description 
 * 		Given an integer, convert it to a roman numeral.
 * 
 * 		Input is guaranteed to be within the range from 1 to 3999.
 */
public class IntegerToRoman {

	public String solution1(int num) {
		char[] symbol = { 'M', 'D', 'C', 'L', 'X', 'V', 'I' };
		int[] base = { 1000, 500, 100, 50, 10, 5, 1};
		int index = 0;
		int counter = 0;
		StringBuilder res = new StringBuilder();
		
		while (index < symbol.length) {
			if (num - base[index] >= 0) {
				num -= base[index];
				counter++;
			} else {
				if(counter == 4){  
                    res.append(symbol[index]);  
                    res.append(symbol[index - 1]);  
                    counter = 0;  
                } else if(counter >= 5 && counter < 9){  
                    res.append(symbol[index - 1]);  
                    counter -= 5;  
                } else if(counter == 9){  
                    res.append(symbol[index]);  
                    res.append(symbol[index - 2]);  
                    counter = 0;  
                }  
                while(counter > 0){  
                    res.append(symbol[index]);  
                    counter--;  
                }  
                index += 2;  
			}
		}
		return res.toString();
	}
	
	public String solution2(int num) {
		StringBuilder res = new StringBuilder("");  
        String digit[] = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X",  
                "IX", "V", "IV", "I" };  
        int values[] = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };  
        for(int i = 0; i < 13; i++){  
            while(num >= values[i]){  
                res.append(digit[i]);  
                num -= values[i];  
            }  
        }  
        return res.toString();  
	}
	
}
